package com.lw.leetcode.other.c;

/**
 * Created with IntelliJ IDEA.
 * other
 * 1210. 穿过迷宫的最少移动次数
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/5 21:49
 */
public class MinimumMoves {

    public static void main(String[] args) {
        MinimumMoves test = new MinimumMoves();

        // 9
        int[][] arr = {{0, 0, 0, 0, 0, 1}, {1, 1, 0, 0, 1, 0}, {0, 0, 0, 0, 1, 1}, {0, 0, 1, 0, 1, 0}, {0, 1, 1, 0, 0, 0}, {0, 1, 1, 0, 0, 0}};
        int i = test.minimumMoves(arr);

        System.out.println(i);
    }

    public int minimumMoves(int[][] grid) {
        int length = grid.length;
        long[][] arr = new long[length][length];
        arr[0][0] = 1;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                int item = grid[i][j];
                if (item == 1) {
                    continue;
                }
                long v = arr[i][j];
                int a = (int) v;
                int b = (int) (v >> 32);
                if (a == 0 && b == 0) {
                    continue;
                }
                if (a != 0) {
                    if (j + 2 != length && grid[i][j + 2] == 0) {
                        int n = (int) arr[i][j + 1];
                        if (n == 0 || n > a + 1) {
                            arr[i][j + 1] = arr[i][j + 1] - n + a + 1;
                        }
                    }
                    if (i + 1 != length && grid[i + 1][j] == 0 && grid[i + 1][j + 1] == 0) {
                        int n = (int) arr[i + 1][j];
                        if (n == 0 || n > a + 1) {
                            arr[i + 1][j] = arr[i + 1][j] - n + a + 1;
                        }

                        n = b;
                        if (n == 0 || n > a + 1) {
                            arr[i][j] = arr[i][j] - ((long) n << 32) + ((long) (a + 1) << 32);
                            b = a + 1;
                        }
                    }
                }
                if (b != 0) {
                    if (i + 2 != length && grid[i + 2][j] == 0) {
                        int n = (int) (arr[i + 1][j] >> 32);
                        if (n == 0 || n > b + 1) {
                            arr[i + 1][j] = arr[i + 1][j] - ((long) n << 32) + ((long) (b + 1) << 32);
                        }
                    }
                    if (j + 1 != length && grid[i][j + 1] == 0 && grid[i + 1][j + 1] == 0) {
                        int n = (int) (arr[i][j + 1] >> 32);
                        if (n == 0 || n > b + 1) {
                            arr[i][j + 1] = arr[i][j + 1] - ((long) n << 32) + ((long) (b + 1) << 32);

                        }
                        n = a;
                        if (n == 0 || n > b + 1) {
                            arr[i][j] = arr[i][j] - n + b + 1;
                            a = b + 1;
                            if (n == 0) {
                                if (j + 2 != length && grid[i][j + 2] == 0) {
                                    n = (int) arr[i][j + 1];
                                    if (n == 0 || n > a + 1) {
                                        arr[i][j + 1] = arr[i][j + 1] - n + a + 1;
                                    }
                                }
                                n = (int) arr[i + 1][j];
                                if (n == 0 || n > a + 1) {
                                    arr[i + 1][j] = arr[i + 1][j] - n + a + 1;
                                }
                            }
                        }

                    }
                }
            }
        }
        return (int) arr[length - 1][length - 2] - 1;
    }

}
